#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100004
int a[N]={0};
int b[N]={0};
int c[N]={0};
char t[N];
int lena,lenb,lenc;
void jian(int a[N])
{
	int i,j=1;
	for(i=0;i<lenb;i++)
	{
		b[i]=a[i]-j;
		if(b[i]>=0)
			j=0;
		else
			b[i]=9;
	}
	if(b[i-1]==0)
		lenb--;
}
void jc(int a[N],int b[N])
{
	int i,j;
	for(i=0;i<lenb;i++)
	{
		for(j=0;j<lena;j++)
		{
			c[i+j]+=a[j]*b[i];
		}
	}
	lenc=lena+lenb;
	for(i=0;i<lenc;i++)
	{
		if(c[i]>=10)
		{
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	}
	if(c[i-1]==0)
		lenc--; 
}
void copy(int a[N],int c[N])
{
	int i,j;
	for(i=0;i<lenc;i++)
		a[i]=c[i];
	lena=lenc;
}

int main()
{
	int m,i,j=0,k=0,n;
	scanf("%d",&m);getchar();
	while(m--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		lena=lenb=lenc=0;
		j=0;k=0;
		scanf("%s",t);getchar();
		n=atoi(t);
		for(i=strlen(t)-1;i>=0;i--)
			a[j++]=b[k++]=t[i]-'0';
	
		lena=lenb=j;
		for(i=n-1;i>=1;i--)
		{
			jian(b);
			jc(a,b);
			copy(a,c);
			memset(c,0,sizeof(c));
		}
		printf("%d\n",lenc);
	}
	return 0;
}
